package com.squirrel.michale.search5;
/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/1/18 12:15 PM
 * @company Michale Squirrel
 * @link
 * @description
 */


/**
 * 875. 爱吃香蕉的珂珂
 * 中等
 * 461
 * 相关企业
 * 珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
 *
 * 珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
 *
 * 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
 *
 * 返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
 *
 *
 *
 * 示例 1：
 *
 * 输入：piles = [3,6,7,11], h = 8
 * 输出：4
 * 示例 2：
 *
 * 输入：piles = [30,11,23,4,20], h = 5
 * 输出：30
 * 示例 3：
 *
 * 输入：piles = [30,11,23,4,20], h = 6
 * 输出：23
 *
 *
 * 提示：
 *
 * 1 <= piles.length <= 104
 * piles.length <= h <= 109
 * 1 <= piles[i] <= 109
 *
 *
 * 此题是典型的二分猜答案模板题，类似的题目或可以用这个方法求解的题目还有275. H 指数 II，611. 有效三角形的个数，1011. 在 D 天内送达包裹的能力，1482. 制作 m 束花所需的最少天数等
 */
public class LeetCode0875 {


    /**
     * [1,1,1,999999999]
     * 10
     * 这个测试用例没过
     *
     * @param piles
     * @param h
     * @return
     */
    public int minEatingSpeed(int[] piles, int h) {

        int left = 1;
        int right = getMax(piles);

        int middle = 0;
        int speed = right;
        while (left <= right) {
            middle = left + ((right - left) >> 1);

            int realTime = getSpendTime(piles, middle);
            if (h > realTime) {
                right = middle-1;
                speed = middle < speed ? middle : speed;
            } else if (h == realTime) {
                left = middle+1;
                speed = middle < speed ? middle : speed;
            } else {
                left = middle+1;
            }
        }

        return speed;

    }

    public int getMax(int[] piles) {
        int max = 0;
        for (int i = 0; i < piles.length; i++) {
            max = piles[i] > max ? piles[i] : max;
        }
        return max;
    }

    public int getSpendTime(int[] piles,int speed) {
        int totalTime = 0;
        for (int i = 0; i < piles.length; i++) {
            totalTime += piles[i]/speed + (piles[i]%speed > 0?1:0);
        }
        return totalTime;
    }


    /**
     * [805306368,805306368,805306368]
     * 1000000000
     * 这个测试用例没过
     *
     * 输出
     * 1
     * 预期结果
     * 3
     * @param piles
     * @param h
     * @return
     */
    public int minEatingSpeed2(int[] piles, int h) {

        int left = 1;
        int right = getMax(piles);

        int middle = 0;
        int speed = right;
        while (left <= right) {
            middle = left + ((right - left) >> 1);

            long realTime = getSpendTime2(piles, middle);
            if (h >= realTime) {
                right = middle-1;
                speed = middle < speed ? middle : speed;
            } else {
                left = middle+1;
            }
        }

        return speed;

    }


    public long getSpendTime2(int[] piles,int speed) {
        long totalTime = 0;
        for (int i = 0; i < piles.length; i++) {
            totalTime += (piles[i]+speed -1)/speed;
        }
        return totalTime;
    }

    public static void main(String[] args) {

        int[] piles = new int[]{3, 6, 7, 11};

        LeetCode0875 leetCode0875 = new LeetCode0875();

//        System.out.println(leetCode0875.minEatingSpeed(piles, 8));
//
//
//        int[] piles2 = new int[]{30,11,23,4,20};
//
//        System.out.println(leetCode0875.minEatingSpeed(piles2, 5));
//
//        int[] piles3 = new int[]{30,11,23,4,20};
//
//        System.out.println(leetCode0875.minEatingSpeed(piles3, 6));



        int[] piles4 = new int[]{1,1,1,999999999};
//
//        System.out.println(leetCode0875.minEatingSpeed(piles4, 10));

        //我的答案156250000
        //正确答案142857143


//        System.out.println(leetCode0875.minEatingSpeed2(piles4, 10));

        //我的答案156250000
        //正确答案142857143

        int[] piles5 = new int[]{805306368,805306368,805306368};
        // getSpendTime溢出，用long接收
        //int的取值范围为:-2^31 ---- 2^31-1 ,即:-2147483648 - 2147483647
        //805306368*3 = 2415919104
        // 2147483647/3 = 715827882.333333333333333

        System.out.println(leetCode0875.minEatingSpeed2(piles5, 1000000000));



    }
}
